package vn.edu.hcmut.cse.ai.search.local;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import vn.edu.hcmut.cse.ai.infrastructure.Action;
import vn.edu.hcmut.cse.ai.infrastructure.Node;
import vn.edu.hcmut.cse.ai.infrastructure.Problem;
import vn.edu.hcmut.cse.ai.infrastructure.Solution;
import vn.edu.hcmut.cse.ai.search.SearchAlgorithm;

/**
 * The blocks world problem is a special problem that it has a holding state
 * that is hard to calculate the heuristic point. So, we have to implement this
 * special searching class for the blocks world problem. In this class, the
 * nodes expanded would have two steps, skipping the holding state.
 *
 * @author MinhLuan
 */
public class BlocksWorldSimpleHillClimbing implements SearchAlgorithm {

    private final HeuristicFunction heuristicFunction;

    public BlocksWorldSimpleHillClimbing(HeuristicFunction heuristicFunction) {
        this.heuristicFunction = heuristicFunction;
    }

    @Override
    public List<Action> doSearching(Problem problem) {
        Node rootNode = new Node(problem.getInitialState(), null, null);
        double initialDistance = this.heuristicFunction.heuristicEvaluation(problem.getInitialState(), problem.getGoalTest().getGoalState());
        rootNode.setHeuristicPoint(initialDistance);

        // Add a hash set to reduce the expanded node list
        HashSet<Object> exploredSet = new HashSet<>();
        exploredSet.add(rootNode.getState());

        Node currentNode = rootNode;
        boolean canFindBetterNode;
        while (true) {
            canFindBetterNode = false;
            if (problem.getGoalTest().isGoalState(currentNode.getState())) {
                return new Solution(currentNode).getActionList();
            }

            // Find the expanded nodes of the current node
            List<Node> expandedNodes = expandNode(currentNode, problem, exploredSet);

            // Loop for all expanded nodes to find a better node
            for (int i = 0; i < expandedNodes.size(); i++) {
                Node childNode = expandedNodes.get(i);
                childNode.setHeuristicPoint(this.heuristicFunction.heuristicEvaluation(childNode.getState(), problem.getGoalTest().getGoalState()));

                if (currentNode.getHeuristicPoint() < childNode.getHeuristicPoint()) {
                    canFindBetterNode = true;
                    currentNode = childNode;
                    exploredSet.add(currentNode.getState());
                    break;
                }
            }

            if (canFindBetterNode == false) {
                break;
            }
        }
        return new ArrayList<>();
    }

    /**
     * Assume that the current state is not a holding state
     *
     * @param node
     * @param problem
     * @return The expanded nodes of the current node skipping the holding state
     */
    private List<Node> expandNode(Node node, Problem problem, HashSet<Object> exploredSet) {
        List<Node> firstExpandedNodeList = new LinkedList<>();
        List<Node> secondExpandedNodeList = new LinkedList<>();
        List<Action> actionList = problem.getActions().getActionList(node.getState());

        for (Action anAction : actionList) {
            Node childNode = problem.getChildNode(node, anAction);
            firstExpandedNodeList.add(childNode);
        }

        while (firstExpandedNodeList.isEmpty() == false) {
            Node aNode = firstExpandedNodeList.remove(0);
            List<Action> secondActionList = problem.getActions().getActionList(aNode.getState());
            for (Action secondAction : secondActionList) {
                Node secondChildNode = problem.getChildNode(aNode, secondAction);
                if (!exploredSet.contains(secondChildNode.getState())) {
                    secondExpandedNodeList.add(secondChildNode);
                }
            }
        }

        // Shuffle the list to make it random
        Collections.shuffle(secondExpandedNodeList);

        return secondExpandedNodeList;
    }
}
